This invention relates generally to the transmission and detection of digital data using analog signals, and more particularly the invention relates to the detection of phase shift keying (PSK) encoded digital data.
The phase of a carrier signal can be used to encode digital data for transmission. The number of bits represented by a carrier phase symbol depends on the number of phases M of the carrier in an MPSK data burst.
A prior art approach to the detection of data symbols consists of using a phase locked loop to lock to the reference symbols and then detecting the data symbols using the phase reference out of the loop. A related approach is to use both reference symbols and remodulated data symbols to obtain a loop phase reference. These approaches are well known.
Another approach is to form a phase reference using a filtering operation on the reference symbols, often called pilot symbol aided demodulation. This approach is essentially the same as the phase locked loop approach in the sense that the phase locked loop also performs a filtering operation.
The present invention is concerned with maximum likelihood detection of data symbols in an MPSK data burst with inserted reference symbols.
The present invention presents a fast algorithm to perform maximum likelihood detection of data symbols. The figures of the drawings (FIGS. 1A, 1B, 2, 3A, 3B) illustrate flow diagrams of four embodiments in implementing algorithm.
First consider a specific problem which however has all the essential features of the general problem. Consider that N data symbols s1, s2, . . . sN are transmitted at times 1, 2, . . . N, and that a reference symbol sN+1 is transmitted at time N+1. All N+1 symbols are MPSK symbols, that is, for k=1, . . . N, sk=ejxcfx86k, where xcfx86k is a uniformly distributed random phase taking values in {0,2xcfx80/M, . . . 2xcfx80(Mxe2x88x921)/M}, and for k=N+1, reference symbol sN+1 is the MPSK symbol ej0=1. The N+1 symbols are transmitted over an AWGN (Additive white Gaussian noise) channel with unknown phase, modeled by the equation:
r=sejxcex8+n.xe2x80x83xe2x80x83(1)
where r, s, and n are N+1 length sequences whose kth components are rk, sk, and nk, respectively, k=1, . . . N+1. Further, n is the noise sequence of independent noise samples, r is the received sequence, and xcex8 is an unknown channel phase, assumed uniformly distributed on (xe2x88x92xcfx80,xcfx80].
We now give the maximum likelihood decision rule to recover the data s1, . . . sN. For the moment, first consider the problem where we want to recover s=s1, . . . sN+1, where sN+1 is assumed to be unknown. We know that the maximum likelihood rule to recover s is the s which maximizes p(r|s). From previous work, we know that this is equivalent to finding the s which maximizes xcex7(s), where:                               η          ⁡                      (            s            )                          =                                            "LeftBracketingBar"                                                ∑                                      k                    =                    1                                                        N                    +                    1                                                  ⁢                                                      r                    k                                    ⁢                                      s                    k                    *                                                              "RightBracketingBar"                        2                    .                                    (        2        )            
In general, there are M solutions to (2). The M solutions only differ by the fact that any two solutions are a phase shift of one another by some multiple of 2xcfx80/M modulo 2xcfx80. Now return to the original problem which is to recover the data s1 . . . sN. The maximum likelihood estimate of s1, . . . sN must be the first N components of the unique one of the M solutions of (2) whose sN+1 component is ej0=1.
An algorithm to maximize (2) when all sk, k=1, . . . N+1 are unknown and differentially encoded is given in K. Mackenthun Jr., xe2x80x9cA fast algorithm for multiple-symbol differential detection of MPSKxe2x80x9d, IEEE Trans. Commun., vol 42, no. 2/3/4, pp. 1471-1474, February/March/April 1994. Therefore to find the maximum likelihood estimate of s1, . . . sN when sN+1 is a reference symbol, we only need to modify the algorithm for the case when sN+1 is known.
The modified algorithm to find the maximum likelihood estimate ŝ1, . . . ŝN of s1, . . . sN is as follows. Let "PHgr" be the phase vector "PHgr"=(xcfx861, . . . xcfx86N+1), where all xcfx86k can take arbitrary values, including xcfx86N+1. If |rk|=0, arbitrary choice of sk will maximize (2). Therefore, we may assume with no loss in generality that |rk| greater than 0, k=1, . . . N. For a complex number xcex3, let arg[xcex3] be the angle of xcex3.
Let =(1, . . . N+1) be the unique "PHgr" for which:
arg[rkexe2x88x92j"psgr"k]xcex5[0,2xcfx80/M),
for k=1, . . . N+1. Define zk by:
zk=rkexe2x88x92jxe2x88x92{tilde over ("psgr")}k.xe2x80x83xe2x80x83(3)
For each k, k=1, . . . N+1, calculate arg[zk]. List the values arg[zk] in order, from largest to smallest. Define the function k(i) as giving the subscript k of zk for the ith list position, i=1, . . . N+1. Thus, we have:                     0        ≤                  arg          ⁡                      [                          z                              k                ⁡                                  (                                      N                    +                    1                                    )                                                      ]                          ≤                  arg          ⁡                      [                          z                              k                ⁡                                  (                  N                  )                                                      ]                          ≤        …        ≤                  arg          ⁡                      [                          z                              k                ⁡                                  (                  1                  )                                                      ]                           less than                                             2              ⁢              π                        M                    .                                    (        4        )            
For i=1, . . . N+1, let:
gi=zk(i).xe2x80x83xe2x80x83(5)
For i satisfying N+1 less than ixe2x89xa62(N+1), define:
xe2x80x83gi=exe2x88x92j2xcfx80j2gixe2x88x92(N+1).xe2x80x83xe2x80x83(6)
Calculate:                                           "LeftBracketingBar"                                          ∑                                  i                  =                  q                                                  q                  +                  N                                            ⁢                              g                i                                      "RightBracketingBar"                    2                ,                  xe2x80x83                ⁢                              for            ⁢                          xe2x80x83                        ⁢            q                    =          1                ,                              …            ⁢                          xe2x80x83                        ⁢            N                    +          1                ,                            (        7        )            
and select the largest.
Suppose the largest magnitude in (7) occurs for q=qxe2x80x2. We now find the phase vector  corresponding to q=qxe2x80x2. Using (3), (5), and (6), with i in the range of qxe2x80x2xe2x89xa6ixe2x89xa6qxe2x80x2+N, we have:
k(i)=k(i),qxe2x80x2xe2x89xa6ixe2x89xa6N+1xe2x80x83xe2x80x83(8)
                                                                        ϕ                                  ~                  ~                                                            k                ⁡                                  (                                      i                    -                    N                                    )                                                      =                                                            ϕ                  ~                                                  k                  ⁡                                      (                                          i                      -                                              [                                                  N                          +                          1                                                ]                                                              )                                                              +                                                2                  ⁢                  π                                M                                              )                ,                              N            +            1                     less than           i          ≤                                    q              xe2x80x2                        +                          N              .                                                          (        9        )            
The evaluation of (8) and (9) gives elements k(l), 1=1, . . . N+1, in order of subscript value k(1), by arranging the elements k(l), l=1, . . . N+1 in order of subscript value k(l), we form the sequence 1, 2, . . . , N+1, which is the vector . The maximum likelihood estimate of ŝ1, . . . ŝN is now given by ŝkejk, . . . k=1, . . . N, where k=kxe2x88x92N+1, k=1, . . . N.
As discussed in Mackenthun supra, algorithm complexity is essentially the complexity of sorting to obtain (4), which is (N+1)log(N+1) operations.
We now expand the specific problem considered earlier to a more general problem. Suppose that N data symbols are transmitted followed by L reference symbols sN+1, . . . sN+L, where sk=ej0=1 for k=N+1, . . . N+L, and assume the definition of channel model (1) is expanded so that r, s, and n are N+L length sequences. Then in place of (2) we have:                               η          ⁡                      (            s            )                          =                                            "LeftBracketingBar"                                                ∑                                      k                    =                    1                                                        N                    +                    L                                                  ⁢                                                      r                    k                                    ⁢                                      s                    k                    *                                                              "RightBracketingBar"                        2                    .                                    (        10        )            
However, note that (10) can be rewritten as:                               η          ⁡                      (            s            )                          =                              "LeftBracketingBar"                                                            ∑                                      k                    =                    1                                    N                                ⁢                                                      r                    k                                    ⁢                                      s                    k                    *                                                              +                                                r                                      N                    +                    1                                    xe2x80x2                                ⁢                                  s                                      N                    +                    1                                    *                                                      "RightBracketingBar"                    2                                    (        11        )            
where rxe2x80x2N+1=rN+1+rN+2+ . . . rN+L. But we can apply the previous modified algorithm exactly to (11) and thereby obtain a maximum likelihood estimate of the first N data symbols.
Now suppose the L reference symbols can take values other than ej0. Since the reference symbols are known to the receiver, we can remodulate them to ej0 and then obtain a result in the form (11), and apply the previous algorithm. Finally, suppose the L reference symbols are scattered throughout the data. It is clear that we can still obtain a result in the form (11) and apply the previous algorithm.
If desired, sorting can be avoided at the expense of an increase in complexity in the following way. Fix j, jxcex5{1, . . . N+1}. For k=1, . . . N+1, form rj*rk and let gj,k be the remodulation of rj*rk such that gj,kxcex5{0,2xcfx80/M}. Now note that the set in (7) is the same as the set:                                           "LeftBracketingBar"                                          ∑                                  k                  =                  1                                                  N                  +                  1                                            ⁢                              g                                  j                  ,                  k                                                      "RightBracketingBar"                    2                ,                  xe2x80x83                ⁢                              for            ⁢                          xe2x80x83                        ⁢            j                    =          1                ,                              …            ⁢                          xe2x80x83                        ⁢            N                    +          1.                                    (        12        )            
Thus, sorting has been eliminated but forming the above set requires (N+1)2 complex multiplications.